package main

import "fmt"

/**
 * @param triangle: a list of lists of integers
 * @return: An integer, minimum path sum
 */
func MinimumTotal(triangle [][]int) int {
	if triangle == nil {
		return 0
	}

	rows := len(triangle)
	if rows == 1 {
		return triangle[0][0]
	}

	for i := rows - 2; i >= 0; i-- {
		for j := 0; j < len(triangle[i]); j++ {
			cur := triangle[i+1][j]
			if cur > triangle[i+1][j+1] {
				cur = triangle[i+1][j+1]
			}
			triangle[i][j] += cur
		}
	}

	return triangle[0][0]
}

func main() {
	arr := [][]int{
		{2},
		{3, 4},
		{6, 5, 7},
		{4, 1, 8, 3},
	}

	fmt.Println(MinimumTotal(arr))
}
